1. Field of the Invention
The present invention relates to collaborative planning actions and recipes.
2. Background
Collaboration of multiple agents to solve problems is an area of active research. Collaboration, in this context, is a special type of coordinated activity in which the agents attempt to achieve a shared goal. The agents work with each other, performing a task or activities needed to satisfy a shared goal.
Collaborative behavior is arguably synergistic in nature, that is, such behavior can be more than the sum of individual acts. Collaboration may be distinguished from both interaction and simple coordination in terms of the mutual commitments agents make to achieve an agreed result. Collaboration is arguably a system feature that must be inherently designed, rather than being subsequently added.
When multiple agents work together in collaboration to accomplish certain tasks, the agents create plans to perform these tasks and, ultimately, the agents execute their plans. A collaborative task in which software agents are expected to participate has certain characteristics. These characteristics can be listed as: (i) limited resources (including, for example, time constraints), (ii) multiple levels of action decomposition, (iii) a combination of group and individual activities, (iv) partial knowledge on the part of each agent, and (v) the need for coordination and negotiation between agents.
To understand the nature of collaborative tasks, and the importance of planning in the whole process, consider the following scenario. A network of computers is used for scientific computing. The network administrator (NA) needs to analyze processor and disk usage in the network to rearrange the clusters and hence obtain better performance from the network. Assume that there is a single maintenance port open on each node, where queries regarding system usage can be made. A constraint is specified that only one query can be running at any particular time on a node.
In this case, the NA uses two maintenance agents (that is, software agents) and commands these agents to work together to report of CPU usage and disk usage on various nodes in the network. For convenience, the software agents used in the following example are referred to as Jack and Jill.
Jack and Jill jointly decide that Jack will collect the CPU usage statistics from the network, and Jill will collect the disk usage statistics from the network, and that Jack and Jill will jointly prepare a final report to be submitted to the NA. These three subactions (namely: (i) collecting the CPU statistics, (ii) collecting the disk usage statistics, and (iii) prepare the final report) constitute a high level recipe for carrying out the action specified by the NA.
Other recipes could be devised for the same task. Such alternative recipes may involve deciding to divide the set of nodes into two and each agent handles both the CPU and disk queries for the subset of nodes to which the agent is committed, and then combining and submitting the results.
After a recipe is established and agreed upon, Jack and Jill must each form their own individual plan. Jack's plan is for collecting CPU statistics and Jill's plan is for collecting the disk usage statistics. Jack and Jill need not know the complete details of each other's plans, but each need to avoid conflicts arising between their respective plans. For example, Jack and Jill must negotiate on their itinerary for visiting the nodes so that their itineraries do not clash. Thus, as the agents develop their individual plans, each agent must watch for potential conflicts with the plans of other agents, and coordinate with potentially conflicting agents as required. Further, Jack and Jill need to have a shared plan for the third action, namely preparing the final report.
Each of these three actions outlined above in the recipe is complex, in the sense that the recipe requires further decomposition. Hence, Jack must develop a recipe for collecting CPU usage statistics, which will likely involve visiting a node and executing a particular command on the maintenance port. Similarly, Jill must develop a recipe for collecting disk usage statistics. Jack and Jill must then develop, negotiate and agree upon a plan for preparing the report, which is to be performed together. This recipe might specify that each agent push the data collected for each node into a database, and then format the report from his data using routines provided by the database management system.
Alternatively, since Jack and Jill are not specialists in writing and formatting reports, Jack and Jill might decide to contract this action of formatting the report to another agent, named here for convenience as ReporterAgent. ReporterAgent's contract is to fetch the data from the database (once, of course, Jack and Jill have pushed the relevant statistics into different tables of the database), and use a word processing application to prepare a suitably formatted report.
Various other specific examples of agent-based collaborate planning tasks exist. Several important points can be drawn from the above example, and other such examples. First, plans are not just recipes. Recipes only specify how to perform an action. Consequently, considerations that must be taken into account during planning include: (i) whether an agent intends to perform the actions, (ii) whether the agent is capable of performing the actions, (111) whether the agent believes so, (iv) whether the agent decides to contract out a particular action, (v) the commitment that the agent has towards the success of the group, and (vi) the means-ends reasoning that results because of this mutual commitment between agents.
Second, each agent is an autonomous entity. Each agent has particular recipe library and is aware of the actions that the agent can perform and, by omission, those actions that the agent cannot perform. There is no central controlling or coordinating authority and hence the intelligence required in performing the tasks collaboratively is completely distributed.
The formalization of collaborative planning primarily concerns modeling the “mental states” of agents involved in collaborative activities. These mental state specifications constitute individual and shared plans for agents. Efforts to formalize the principles of collaborative planning also include specifying the capability to act, mental attitudes such as beliefs and intentions required for participants in a group activity, specification of individual and shared plans. Set theory and first order logic can be used to present formal models of plans and other mental states of agents.
The following lists enumerate major components of individual and group plans. These principles and components are the entities that are modelled during formalization.
To have an individual plan for an action, one needs:
(i) knowledge of a recipe,
(ii) ability to perform subactions, and
(iii) intentions to do the subactions.
To have a group plan for an action, one needs:
(i) mutual belief of a recipe,
(ii) individual or group plans for the subactions,
(iii) intentions that group perform actions, and
(iv) intentions that collaborators succeed.
Formalization modeling the above elements of a plan (individual or group) provides a theoretical foundation to build multi-agent systems for a variety of practical applications. Modeling also helps in validating and verifying key results in the field of collaborative planning.